package Heap;

import java.util.*;

public class TestHeap {

    // 用数组来存储 堆
    public int[] elem;
    public int usedSize;

    public TestHeap(){
        elem=new int[10];
    }

    public void initHeap(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            elem[i]=arr[i];
            usedSize++;
        }
    }


    // 通过数组建立 大根堆
    public void creatHeap(int[] array){

        for(int parent=(usedSize-1-1)/2;parent>=0;parent--){
            shiftDown(parent,array.length);
        }
    }
    // 向下
    private void shiftDown( int parent,int len){
        //  用child 来表示parent 的左孩子
        int child=parent*2+1;
        while(child<len) {
            if (child + 1 < len && elem[child] < elem[child + 1]) {
                child = child + 1;
            }
            // 到这里，child 表示parent的左右孩子中较大数据的下标，
            // 如果 child大于parent ，那就进行交换
            if (elem[child] > elem[parent]) {
                swap(child, parent);
                parent=child;
                child=2*parent+1;
            }else{
                break;
            }
        }
    }
    // 用来交换i 和j位置的数据
    private void swap(int i,int j){
        int tmp=elem[i];
        elem[i]=elem[j];
        elem[j]=tmp;
    }

    public void push(int key){
        shiftUp(key);
    }


    // 堆中插入元素:向上
    private void shiftUp(int key){
        // 判断是否满了
        if(isFull()){
            elem= Arrays.copyOf(elem,2*elem.length);
        }
        // 尾部插入元素
        elem[usedSize]=key;
        usedSize++;
        int child=usedSize-1;

        // 在进行调整，调整成大根堆
        int parent=(child-1)/2;
        while(child>=0&& parent>=0){
            // 此处只用跟父亲节点比较即可
            if(elem[parent]<elem[child]){
                swap(parent,child);
                child =parent;
                parent=(child-1)/2;
            }else{
                break;
            }
        }

    }

    private boolean isFull(){
        return usedSize==elem.length;
    }


    public int pop(){
        if(isEmpty()){
            throw new EmptyException(" 大根堆空，异常");
        }
        // 将要输出的数据换到最后
        int tmp=elem[0];
        swap(0,usedSize-1);
        usedSize--;
        // 在将剩余的数据按照规排好
        shiftDown(0,usedSize);

        return tmp;
    }
    public boolean isEmpty(){
        return usedSize==0;
    }


    // 求最小 k 个数
    public int[] smallestK(int[] arr, int k) {
        if(arr == null){
            return arr;
        }
        // 在这里创建了一个优先级队列，这里定义了一个匿名类实现了comoarator的接口，重写了compare接口，实现大根堆
        PriorityQueue<Integer> q=new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        // 建立一个大小为k的根堆
        for(int i=0;i<k;i++){
            q.offer(arr[i]);
        }
        int[] ret=new int[k];
        // 将剩余的节点与 根堆 中 堆顶元素进行比较，在进行大根堆的规则进行排序
        for(int i=k;i<arr.length;i++){
            int top=q.peek();
            if(arr[i]<top){
                q.poll();
                q.offer(arr[i]);
            }
        }
        for(int i=0;i<k;i++){
            ret[i] =q.poll();
        }
        return ret;
    }

    // 升序 ： 建立大根堆，
    public void heapSort(){
        int end=usedSize-1;
        while(end>0){
            swap(0,end);
            // 此时最后一个就是最大的节点
            shiftDown(0,end);
            end--;
        }
    }
}
